/**
 * 项目名称: Topic_75.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第十天 数组+双指针
 * 编辑时间: 2024年09月11日19时16分29秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int nums_1  = 0, nums_2 = 0,nums_3 = 0;
//        for(int i = 0;i<nums.size();i++){
//            if(nums[i] == 0)nums_1++;
//            else if(nums[i] == 1)nums_2++;
//            else nums_3++;
//        }
//
//        for(int i = 0;i<nums.size();i++){
//            if(i<nums_1)nums[i]=0;
//            else if(i<nums_1+nums_2)nums[i]=1;
//            else nums[i]=2;
//        }
//
//    }
//};

/*
 * 荷兰国旗问题:
 * 将整个数组分为三段:
 *  向右扫描两段:
 *  0~j-1 全为 0 ; j~i-1 全为 1
 *  向左扫描一段:
 *  k-1 ~ n-1 全为 2
 *
 *  当 i > k 时说明遍历完毕
 * 以 i为基准分为三种情况:
 *  - 当v[i] = 0 将 i 和 j交换,然后 j++,i++ (可以进行交换是因为当便利到j的时候得到的就是已经便利好的)
 *  - 当v[i] = 2 将 i 和 k交换,然后 k--, 交换后 v[i]的值不确定,所以不用++
 *  - 当v[i] = 1 将 i++ 即可
 */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i = 0,j = 0,k = nums.size()-1;i<=k;){
            if(nums[i] == 0)swap(nums[i++],nums[j++]);
            else if(nums[i] == 2) swap(nums[i],nums[k--]);
            else i++;
        }
    }
};
